package Leetcode.DayTest;
import java.util.Scanner;

public class Mi_2023 {

    // 定义节点类，用于存储区间信息
    static class Node {
        int i; // 区间编号
        boolean set; // 标记是区间开始还是结束
        Node prev; // 指向上一个节点

        // 构造函数
        public Node(int i, boolean set, Node prev) {
            this.i = i;
            this.set = set;
            this.prev = prev;
        }
    }

    // 定义优先队列类，用于管理区间
    static class PriorityQueue {
        private final boolean[] active; // 标记区间是否活跃
        private int max; // 记录当前最大的区间编号

        // 构造函数
        public PriorityQueue(int upperBound) {
            active = new boolean[upperBound + 1];
            active[0] = true; // 初始化，确保0号位置为活跃状态
            max = 0; // 初始化最大编号为0
        }

        // 添加区间
        public void add(int i) {
            active[i] = true; // 标记区间为活跃
            if (i > max) // 更新最大编号
                max = i;
        }

        // 移除区间
        public void remove(int i) {
            active[i] = false; // 标记区间为非活跃
            if (max == i) // 如果移除的是最大编号的区间，则重新计算最大编号
                while (!active[max]) max--;
        }

        // 获取当前最大的区间编号
        public int peek() {
            return max;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建Scanner对象，用于读取输入
        int n = sc.nextInt(); // 读取区间长度
        int m = sc.nextInt(); // 读取区间数量
        Node[] nodes = new Node[n + 1]; // 创建节点数组，用于存储区间信息

        // 读取区间信息
        for (int i = 1; i <= m; i++) {
            int l = sc.nextInt(); // 区间开始位置
            int r = sc.nextInt(); // 区间结束位置
            nodes[l] = new Node(i, true, nodes[l]); // 在开始位置添加区间开始标记
            nodes[r + 1] = new Node(i, false, nodes[r + 1]); // 在结束位置+1添加区间结束标记
        }

        long res = 0; // 初始化结果
        PriorityQueue pq = new PriorityQueue(m); // 创建优先队列对象

        // 遍历每个位置
        for (int index = 0; index < n; index++) {
            Node node = nodes[index]; // 获取当前位置的节点
            while (node != null) { // 遍历所有相关节点
                if (node.set) { // 如果是区间开始标记，则添加到优先队列
                    pq.add(node.i);
                } else { // 如果是区间结束标记，则从优先队列移除
                    pq.remove(node.i);
                }
                node = node.prev; // 移动到下一个节点
            }
            int a_i = pq.peek(); // 获取当前最大的区间编号
            res = (res + (long) index * a_i) % 100000009L; // 更新结果
        }

        System.out.println(res); // 输出结果
    }


    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int k) {
        if (k == word.length()) {
            return true;
        }
        if (i < 0
                || i >= board.length
                || j < 0
                || j >= board[0].length
                || visited[i][j]
                || board[i][j] != word.charAt(k)) {
            return false;
        }
        visited[i][j] = true;
        boolean res = dfs(board, word, visited, i - 1, j, k + 1) ||
                dfs(board, word, visited, i + 1, j, k + 1) ||
                dfs(board, word, visited, i, j - 1, k + 1) ||
                dfs(board, word, visited, i, j + 1, k + 1);
        visited[i][j] = false;
        return res;
    }


}